package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC909 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int snakesAndLadders(int[][] board) {
            int N = board.length;

            Map<Integer, Integer> distanceMemo = new HashMap();
            distanceMemo.put(1, 0);

            Queue<Integer> queue = new LinkedList();
            queue.add(1);

            while (!queue.isEmpty()) {
                int s = queue.remove();
                if (s == N * N) return distanceMemo.get(s);

                for (int s2 = s + 1; s2 <= Math.min(s + 6, N * N); ++s2) {
                    int rc = get(s2, N);
                    int r = rc / N, c = rc % N;
                    int s2Final = board[r][c] == -1 ? s2 : board[r][c];
                    if (!distanceMemo.containsKey(s2Final)) {
                        distanceMemo.put(s2Final, distanceMemo.get(s) + 1);
                        queue.add(s2Final);
                    }
                }
            }
            return -1;
        }

        /**
         * Given a square num s, return board coordinates (r, c) as r*N + c
         *
         * @param s
         * @param N
         * @return
         */
        public int get(int s, int N) {
            int quot = (s - 1) / N;
            int rem = (s - 1) % N;
            int row = N - 1 - quot;
            int col = row % 2 != N % 2 ? rem : N - 1 - rem;
            return row * N + col;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC909 an = new LC909();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
